//
//  BiTree.cpp
//  DataStruct
//
//  Created by vase on 2022/3/31.
//

#include "BiTree.hpp"

/** 先序遍历--https://leetcode-cn.com/problems/binary-tree-preorder-traversal/*/
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> seq;
    //借用堆栈实现迭代式遍历
    TreeNode *temp = root;
    stack<TreeNode*> stack;
    while (temp!=nullptr || stack.size()!=0) {
        if (temp != nullptr) {
            seq.push_back(temp->val);
            //将当前元素加入堆栈
            stack.push(temp);
            //继续向左子树进发
            temp = temp->left;
        }else {
            //需要把之前吃进去的节点吐出来，把右边的节点回收下
            temp = stack.top();
            stack.pop();
            //遍历右边的节点
            temp = temp->right;
        }
    }
    return seq;
}

/** 中序遍历--https://leetcode-cn.com/problems/binary-tree-inorder-traversal/*/
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> seq;
    //借用堆栈实现迭代式遍历
    TreeNode *temp = root;
    stack<TreeNode*> stack;
    while (temp!=nullptr || stack.size()!=0) {
        if (temp != nullptr) {
            //将当前元素加入堆栈
            stack.push(temp);
            //继续向左子树进发
            temp = temp->left;
        }else {
            //此时已经到达了子树的最左边，将吃进去的节点吐出来，完成先序序列构建
            temp = stack.top();
            stack.pop();
            seq.push_back(temp->val);
            //遍历右边的节点
            temp = temp->right;
        }
    }
    return seq;
}

/** 后序遍历--https://leetcode-cn.com/problems/binary-tree-postorder-traversal/*/
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> seq;
    //借用堆栈实现迭代式遍历
    TreeNode *temp = root;
    stack<TreeNode*> stack;
    //后序遍历需要一个标记节点
    TreeNode *pre = root;
    //关键是要使得左右子树都已经走完的时候，再去叨扰根节点
    while (temp!= nullptr || stack.size()!=0) {
        if (temp != nullptr) {
            //如果可以的，先把左子树走完
            stack.push(temp);
            temp = temp->left;
        }else {
            temp = stack.top();
            stack.pop();
            //如果右子树还没有走，就先去访问右子树
            if (temp->right != nullptr && temp->right != pre) {
                //把节点先塞回去，因为后序要等到右子树走完才能过根节点
                stack.push(temp);
                //遍历右子树
                temp = temp->right;
            }else {
                //右子树为空，或者已经访问过了，可以先把节点加入到序列
                seq.push_back(temp->val);
                //标记位置已经访问过
                pre = temp;
                //把节点置空，使得栈把之前的节点再吐出来一个，返回到上一层
                temp = nullptr;
            }
        }
    }
    return seq;
}

/** 层次遍历--https://leetcode-cn.com/problems/binary-tree-level-order-traversal/*/
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> seqs;
    if (root == nullptr) { //特判空树的情况
        return seqs;
    }
    //使用队列来实现节点的层次遍历
    queue<TreeNode*> nodes;
    nodes.push(root);
    while (nodes.size() != 0) {
        //如果按照我这样写的话，每次循环都是一层节点
        vector<int> seq;
        int size = nodes.size();
        while (size--) {
            //取出队头元素
            TreeNode *now = nodes.front();
            nodes.pop();
            //可以先把元素加入队列
            seq.push_back(now->val);
            //将其左右孩子入队
            if (now->left != nullptr) {
                nodes.push(now->left);
            }
            if (now->right != nullptr) {
                nodes.push(now->right);
            }
        }
        if (seq.size() > 0) {
            seqs.push_back(seq);
        }
    }
    return seqs;
}
